<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<script>
	{
		function compare (a, b) {
			if (a < b) return compare.less
			if (a > b) return compare.great
			if (a === b) return compare.equal
    }
		compare.less = -1
    compare.great = 1
    compare.equal = 0

		class Node {
			constructor(val) {
				this.val = val
        this.left = null
        this.right = null
			}
    }

    class BST {
			root = null
      /* 插入 */
      insert (val) {
				if (this.root) {
					this._insert(this.root, val)
        } else {
					this.root = new Node(val)
        }
      }

			_insert (node, val) {
				if (compare(val, node.val) === compare.less) {
					if (node.left) {
						this._insert(node.left, val)
          } else {
						node.left = new Node(val)
          }
        } else {
					if (node.right) {
						this._insert(node.right, val)
          } else {
						node.right = new Node(val)
          }
        }
      }

			/* 删除 */
      remove (val) {
				if (this.root) {

        }
      }

			removeNode (node, val) {}
      /* 查询 */
      /* 最小值 */
      min () {
				if (this.root) {
					return this.getMin(this.root).val
        }
      }

			getMin (node) {
				let current = node
        while (current.left) {
					current = current.left
        }
				return current
      }
      /* 最大值 */
      max () {
				if (this.root) {
					return this.getMax(this.root).val
        }
      }

			getMax (node) {
				let current = node
				while (current.right) {
					current = current.right
				}
				return current
      }
      /* 前序遍历 */
      /* 中序遍历 */
      /* 后序遍历 */
    }

		const bst = new BST()
		bst.insert(9)
		bst.insert(6)
		bst.insert(4)
		bst.insert(7)
		bst.insert(6.6)
		bst.insert(8)

    // bst.delete(6)
    //
		console.log(bst)
		// console.log(bst.min())
		// console.log(bst.max())

    // bst.preOrderMap((node) => {
	  //   console.log(node.val)
    // })
  }
</script>
</body>
</html>
